package sivan.letcode;

import java.util.*;

public class TreeCode {

    public static void main(String[] args) {
        TreeNode root = new TreeNode("A");
        TreeNode b = new TreeNode("B");
        TreeNode c = new TreeNode("C");
        TreeNode d = new TreeNode("D");
        TreeNode e = new TreeNode("E");
        TreeNode f = new TreeNode("F");
        TreeNode g = new TreeNode("G");
        TreeNode h = new TreeNode("H");
        TreeNode i = new TreeNode("I");

        root.left = b;
        root.right = c;

        b.left = d;
        b.right = e;

        c.left = f;
        c.right = g;

        e.right = i;
        g.left = h;

        List<String> result = printFromTopToBottom(root);
        System.out.println("广度优先算法：" + result);
        List<String> list = printFromDest(root);
        System.out.println("深度优先算法：" + list);

        System.out.println("前序遍历：");
        preOrder(root);

        System.out.println("\n中序遍历：");
        midOrder(root);

        System.out.println("\n后序遍历:");
        postOrder(root);
    }

    public static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + ",");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void midOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        midOrder(root.left);
        System.out.print(root.val + ",");
        midOrder(root.right);
    }

    public static void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + ",");
    }


    /**
     * 二叉树深度优先
     *
     * @param treeNode
     * @return
     */
    public static List<String> printFromDest(TreeNode treeNode) {
        List<String> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(treeNode);
        while (!stack.isEmpty()) {
            TreeNode top = stack.pop();
            result.add(top.val);
            if (top.right != null) {
                stack.push(top.right);
            }
            if (top.left != null) {
                stack.push(top.left);
            }
        }
        return result;
    }

    /**
     * 广度优先算法
     *
     * @param treeNode
     * @return
     */
    public static List<String> printFromTopToBottom(TreeNode treeNode) {
        List<String> result = new ArrayList<>();
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.add(treeNode);
        while (!deque.isEmpty()) {
            TreeNode first = deque.pop();
            result.add(first.val);
            if (first.left != null) {
                deque.add(first.left);
            }
            if (first.right != null) {
                deque.add(first.right);
            }
        }
        return result;
    }

    static class TreeNode {
        String val;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(String val) {
            this.val = val;
        }
    }

}
